package class03;

import java.util.HashSet;

public class Code02_HowManyTypes {

	/*
	 * 只由小写字母（a~z）组成的一批字符串，都放在字符类型的数组String[] arr中，
	 * 如果其中某两个字符串，所含有的字符种类完全一样，就将两个字符串算作一类 比如：baacba和bac就算作一类
	 * 虽然长度不一样，但是所含字符的种类完全一样（a、b、c） 返回arr中有多少类？
	 * 
	 */

	// 方法一：使用字符串作为key来表示字符种类
	// 时间复杂度较高，因为涉及字符串拼接操作
	public static int types1(String[] arr) {
		// 使用HashSet存储不同的字符种类组合，自动去重
		HashSet<String> types = new HashSet<>();
		// 遍历数组中的每个字符串
		for (String str : arr) {
			// 将字符串转换为字符数组
			char[] chs = str.toCharArray();
			// 使用布尔数组记录每个字符是否出现（对应a-z）
			// 索引0表示字符'a'，索引1表示字符'b'，...，索引25表示字符'z'
			boolean[] map = new boolean[26];
			// 遍历字符数组，标记出现的字符
			for (int i = 0; i < chs.length; i++) {
				// chs[i] - 'a' 是将字符转换为相对于'a'的偏移量
				// 例如：'a' - 'a' = 0, 'b' - 'a' = 1, ..., 'z' - 'a' = 25
				// 这样就可以将字符映射到0~25的索引范围
				map[chs[i] - 'a'] = true;
			}
			// 构造表示字符种类的key字符串
			String key = "";
			// 遍历布尔数组，将出现的字符按顺序拼接成字符串
			for (int i = 0; i < 26; i++) {
				// 如果该字符出现过，则拼接到key中
				if (map[i]) {
					// 将索引i转换回对应的字符：i=0对应'a'，i=1对应'b'，...，i=25对应'z'
					key += String.valueOf((char) (i + 'a'));
				}
			}
			// 将key添加到HashSet中
			types.add(key);
		}
		// 返回不同字符种类的数量
		return types.size();
	}

	// 方法二：使用位运算优化的方法
	// 使用一个整数的二进制位表示字符出现情况，效率更高
	public static int types2(String[] arr) {
		// 使用HashSet存储不同的字符种类组合（用整数的二进制位表示）
		HashSet<Integer> types = new HashSet<>();
		// 遍历数组中的每个字符串
		for (String str : arr) {
			// 将字符串转换为字符数组
			char[] chs = str.toCharArray();
			// 使用一个整数的二进制位表示字符出现情况，初始为0
			// 从右往左数，第0位表示字符'a'，第1位表示字符'b'，...，第25位表示字符'z'
			int key = 0;
			// 遍历字符数组，通过位运算标记出现的字符
			for(int i = 0 ; i < chs.length;i++) {
				// chs[i] - 'a' 是将字符转换为相对于'a'的偏移量（0~25）
				// 1 << (chs[i] - 'a') 表示将1左移相应的位数
				// 例如：字符'b'对应偏移量1，1 << 1 = 2 (二进制为10)，表示第1位为1
				// key |= (1 << (chs[i] - 'a')) 表示将对应位设置为1
				key |= (1 << (chs[i] - 'a'));
			}
			// 将表示字符种类的整数添加到HashSet中
			types.add(key);
		}
		// 返回不同字符种类的数量
		return types.size();
	}

	// for test
	// 生成随机字符串数组用于测试
	public static String[] getRandomStringArray(int possibilities, int strMaxSize, int arrMaxSize) {
		// 随机生成数组长度（1到arrMaxSize之间）
		String[] ans = new String[(int) (Math.random() * arrMaxSize) + 1];
		// 为数组每个位置生成随机字符串
		for (int i = 0; i < ans.length; i++) {
			ans[i] = getRandomString(possibilities, strMaxSize);
		}
		return ans;
	}

	// for test
	// 生成随机字符串用于测试
	public static String getRandomString(int possibilities, int strMaxSize) {
		// 随机生成字符串长度（1到strMaxSize之间）
		char[] ans = new char[(int) (Math.random() * strMaxSize) + 1];
		// 随机生成每个字符（从'a'开始的possibilities个字符中选择）
		// (int) (Math.random() * possibilities) 生成0到possibilities-1的随机整数
		// 加上'a'后得到对应的字符，例如0+'a'='a'，1+'a'='b'，...
		for (int i = 0; i < ans.length; i++) {
			ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
		}
		// 将字符数组转换为字符串并返回
		return String.valueOf(ans);
	}

	public static void main(String[] args) {
		int possibilities = 5;
		int strMaxSize = 10;
		int arrMaxSize = 100;
		int testTimes = 500000;
		System.out.println("test begin, test time : " + testTimes);
		// 进行多次测试验证两种方法结果一致性
		for (int i = 0; i < testTimes; i++) {
			// 生成随机测试数据
			String[] arr = getRandomStringArray(possibilities, strMaxSize, arrMaxSize);
			// 分别用两种方法计算结果
			int ans1 = types1(arr);
			int ans2 = types2(arr);
			// 如果结果不一致，说明实现有误
			if (ans1 != ans2) {
				System.out.println("Oops!");
			}
		}
		System.out.println("test finish");

	}

}
